In a computer system, information is typically stored on a non-volatile storage device, such as a hard disk drive or solid-state disk, and cataloged in some hierarchical fashion so that the same information is more easily retrieved when desired. A unique code name, such as a file's name, is attributed to a particular body of data element to differentiate it from others, and the desired body of data is retrievable via the use of the appropriate code name associated with that data. The device can search for that code name and retrieve the desired data when that code name is found. Typically, code names associated with particular data contain pointers, which point to areas in memory reserved for mass storage. The various code names and their pointers comprise a cataloging system used to order the data on the mass storage device. In the case of particularly high-density storage devices, multiple trillions of bytes of information can be stored on such devices. If the multitude of files on such storage devices were required to be managed in a serial fashion, storage operations would be excessively time consuming.
One tool used to manage a complex hierarchical file system is the B-tree data structure. The B-tree data structure is well-known in the prior art and is described in The Art of Computer Programming Volume 3 (Sorting and Searching); by Donald E. Knuth; at Section 6.4; titled “Multiway Trees”; pp 471-479 (1973). The nodes of a B-tree contain records, wherein each record is comprised of certain information, either pointers or data, and a key associated with that record. However, concurrent access to B-tree data structures, and thus, data storage devices featuring file systems managed by B-tree data structures, has been a particular problem, to which several solutions have been attempted. Particular techniques useful for file system B-trees are discussed in an article by Ohad Rodeh in B-trees, Shadowing, and Clones; ACM Transactions on Storage (TOS), Volume 3 Issue 4, February 2008, Article No. 2 and this article is incorporated herein by reference. Several B-tree concurrency techniques are focused on avoiding deadlocks or other broken B-tree states that can result in a file-system malfunction. However, some concurrent access methods can result in a severe performance impact if multiple accesses are attempted.